package org.example.algorithm.doublepointer;

import java.util.Stack;

//接雨水
public class TrapSolution {
    public static void main(String[] args) {
        //int[] height = {2,8,5,5,6,1,7,4,5};
        int[] height = {4, 2, 0, 3, 2, 5};
        //int[] height = {5, 4, 1, 2};
        TrapSolution solution = new TrapSolution();
        int res = solution.trap(height);
        System.out.println(res);
    }

    //单调栈
    public int trap(int[] height) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i=0;i<height.length;i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int width = i - stack.peek() - 1;
                int h = Math.min(height[i], height[stack.peek()]) - height[top];
                ans += width * h;
            }
            stack.push(i);
        }
        return ans;
    }

    //空间优化-双指针
    public int trap3(int[] height) {
        int len = height.length;
        int left = 0;
        int right = len - 1;
        int prefixMax = 0;
        int suffixMax = 0;
        int sum = 0;
        while (left <= right) {
            prefixMax = Math.max(prefixMax, height[left]);
            suffixMax = Math.max(suffixMax, height[right]);
            if (prefixMax > suffixMax) {
                sum += suffixMax - height[right];
                right--;
            } else {
                sum += prefixMax - height[left];
                left++;
            }
        }
        return sum;
    }

    //最大前缀、最大后缀
    public int trap1(int[] height) {
        int len = height.length;
        int[] prefixMax = new int[len];
        prefixMax[0] = height[0];
        int[] suffixMax = new int[len];
        suffixMax[len-1] = height[len-1];
        for (int i=1;i<len;i++) {
            prefixMax[i] = Math.max(prefixMax[i-1], height[i]);
        }
        for (int i=len-2;i>=0;i--) {
            suffixMax[i] = Math.max(suffixMax[i+1], height[i]);
        }
        int sum = 0;
        for (int i=0;i<len;i++) {
            sum += Math.min(prefixMax[i], suffixMax[i]) - height[i];
        }
        return sum;
    }

    //逻辑较为复杂，不建议参考
    public int trap2(int[] height) {
        int left = 0;
        int sum = 0;
        while (left < height.length - 2) {
            //找到下降起始作为start
            if (height[left] <= height[left+1]) {
                left++;
                continue;
            }
            int right = left + 1;
            //尝试找到比>=left的值,并记录right最大值位置
            int tempSum = 0;
            int rightMaxIndex = left+2;
            while (right < height.length && height[right]<height[left]) {
                if (height[right] > height[rightMaxIndex]) {
                    rightMaxIndex = right;
                }
                tempSum += height[right];
                right++;
            }
            //找到>=left的值
            if (right < height.length && height[right] >= height[left]) {
                sum += (right - left - 1) * height[left] - tempSum;
            } else {
                //重置right
                right = rightMaxIndex;
                tempSum = 0;
                int low = Math.min(height[left], height[right]);
                for (int i=left+1;i<right;i++) {
                    tempSum += Math.min(low, height[i]);
                }
                sum += (right - left - 1) * low - tempSum;
            }
            left = right;
        }
        return sum;
    }
}
